class Solution {
public:
    vector<int> tmp;

    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        MergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void MergeSort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return;

        int mid = (r - l) / 2 + l;
        MergeSort(nums, l, mid);
        MergeSort(nums, mid + 1, r);

        int cur1 = l, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= r)
        {
            if (nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
            else tmp[i++] = nums[cur2++];
        }
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= r) tmp[i++] = nums[cur2++];

        for (int k = l; k <= r; k++)
            nums[k] = tmp[k - l];
    }
};